import java.util.*;

/**
 * @author 雷明浩
 * @date 2025/6/26 16:41
 */
public class SerializeTreeNode {
    String Serialize(TreeNode root) {
        // 以层序遍历的方式将二叉树进行序列化
        if (root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        Deque<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        int depth = deepth(root);
        for (int i = 0; i < depth; i++) {
            int size = deque.size();
            for (int j = 0; j < size; j++) {
                TreeNode node = deque.pollFirst();
                if (node != null) {
                    sb.append(node.val);
                } else {
                    sb.append("#");
                }
                sb.append(",");
                if (node != null) {
                    deque.addLast(node.left);
                    deque.addLast(node.right);
                }
            }
        }
        while (sb.charAt(sb.length() - 1) == ',' || sb.charAt(sb.length() - 1) == '#') {
            sb.deleteCharAt(sb.length() - 1);
        }
        return sb.toString();
    }

    TreeNode Deserialize(String str) {
        if (str == null || str.length() == 0) {
            return null;
        }
        String[] ss = str.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(ss[0]));
        Map<Integer, TreeNode> map = new HashMap<>();
        map.put(0, root);
        int count = 0;
        for (int i = 0; i < ss.length; i++) {
            if ("#".equals(ss[i])) {
                count++;
                continue;
            }
            TreeNode node = map.get(i);
            TreeNode leftChild = null;
            int tmp = (int)Math.pow(2, count);
            tmp = tmp == 1 ? 0 : tmp;
            if (2*i+1-tmp < ss.length && !"#".equals(ss[2*i+1-tmp])) {
                leftChild = new TreeNode(Integer.valueOf(ss[2*i+1-tmp]));
            }
            TreeNode rightChild = null;
            if (2*i+2-tmp < ss.length && !"#".equals(ss[2*i+2-tmp])) {
                rightChild = new TreeNode(Integer.valueOf(ss[2*i+2-tmp]));
            }
            node.left = leftChild;
            node.right = rightChild;
            map.put(2*i+1-tmp, leftChild);
            map.put(2*i+2-tmp, rightChild);
        }
        return root;
    }

    private int deepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDeepth = deepth(root.left);
        int rightDeepth = deepth(root.right);
        return Math.max(leftDeepth, rightDeepth) + 1;
    }

    public static void main(String[] args) {
        SerializeTreeNode serializeTreeNode = new SerializeTreeNode();
        String str = "5,4,#,3,#,2";
        TreeNode root = serializeTreeNode.Deserialize(str);
        String ret = serializeTreeNode.Serialize(root);
        System.out.println(str.equals(ret));
    }
}